#include "stdafx.h"
#include "BvhBuilder.h"

#include <cliext\algorithm>


using namespace cliext;
namespace DLLx {
	namespace Bvh {
		static BBox^ WorldBound(TriInfo^ t, const array<Pt^>^ verts)  {
			const Pt ^p0 = verts[t->v1];
			const Pt ^p1 = verts[t->v2];
			const Pt ^p2 = verts[t->v3];
			BBox^ res = BBox::Union(gcnew BBox(p0, p1), p2);
			return res;
		}
		BvhBuilder::BvhBuilder(	const unsigned int vCount, const unsigned int triangleCount, array<TriInfo^>^ t, array<Pt^>^ p,
			const unsigned int treetype, const int csamples, const int icost,
			const int tcost, const float ebonus):costSamples(csamples), isectCost(icost), traversalCost(tcost), emptyBonus(ebonus),
			nPrims(triangleCount)
		{
			points = p;
			triangles = t;

			if (treetype <= 2) treeType = 2;
			else if (treetype <= 4) treeType = 4;
			else treeType = 8;

			cliext::vector<BVHAccelTreeNode^>^ bvList = gcnew cliext::vector<BVHAccelTreeNode^>();
			for (unsigned int i = 0; i < nPrims; ++i) {
				BVHAccelTreeNode^ ptr = gcnew BVHAccelTreeNode();
				ptr->bbox = WorldBound(t[i], p);
				ptr->bbox->Expand(RAY_EPSILON);
				ptr->primitive = i;
				ptr->leftChild = nullptr;
				ptr->rightSibling = nullptr;
				bvList->push_back(ptr);
			}


			//cerr << "Building Bounding Volume Hierarchy, primitives: " << nPrims << endl;

			nNodes = 0;
			BVHAccelTreeNode^ rootNode = BuildHierarchy(bvList, 0, bvList->size(), 2);
			this->debugTree = rootNode;

			//cerr << "Pre-processing Bounding Volume Hierarchy, total nodes: " << nNodes << endl;

			bvhTree = gcnew array<BVHAccelArrayNode^>(nNodes);
			BuildArray(rootNode, 0);

			//cerr << "Finished building Bounding Volume Hierarchy array" << endl;
		};

		bool bvh_ltf_x(BVHAccelTreeNode^ n, float v) {
			return n->bbox->pMax->x + n->bbox->pMin->x < v;
		}

		bool bvh_ltf_y(BVHAccelTreeNode^ n, float v) {
			return n->bbox->pMax->y + n->bbox->pMin->y < v;
		}

		bool bvh_ltf_z(BVHAccelTreeNode^ n, float v) {
			return n->bbox->pMax->z + n->bbox->pMin->z < v;
		}

		bool (* const bvh_ltf[3])(BVHAccelTreeNode ^n, float v) = {bvh_ltf_x, bvh_ltf_y, bvh_ltf_z};

		BVHAccelTreeNode^  BvhBuilder::BuildHierarchy(cliext::vector<BVHAccelTreeNode^>^ list, unsigned int begin, unsigned int end, unsigned int axis)
		{
			unsigned int splitAxis = axis;
			float splitValue;

			nNodes += 1;
			if (end - begin == 1) // Only a single item in list so return it
				return list->at(begin);

			BVHAccelTreeNode^ parent = gcnew BVHAccelTreeNode();
			parent->primitive = 0xffffffffu;
			parent->leftChild = nullptr;
			parent->rightSibling = nullptr;
			/*
			cliext::vector<unsigned int>^ splits = gcnew cliext::vector<unsigned int>();
			splits->reserve(treeType + 1);
			splits->push_back(begin);
			splits->push_back(end);
			for (unsigned int i = 2; i <= treeType; i *= 2) { // Calculate splits, according to tree type and do partition
				for (unsigned int j = 0, offset = 0; j + offset < i && splits->size() > j + 1; j += 2) {
					if (splits->at(j + 1) - splits->at(j) < 2) {
						j--;
						offset++;
						continue; // Less than two elements: no need to split
					}

					FindBestSplit(list, splits->at(j), splits->at(j + 1), splitValue, splitAxis);

					cliext::vector<BVHAccelTreeNode^>::iterator^ it =
						partition(list->begin() + splits->at(j), list->begin() + splits->at(j + 1), bind2nd(ptr_fun(bvh_ltf[splitAxis]), splitValue));
					unsigned int middle = distance(list->begin(), it);
					middle = max(splits->at(j) + 1, min(splits->at(j + 1) - 1, middle)); // Make sure coincidental BBs are still split
					splits->insert(splits->begin() + j + 1, middle);
				}
			}

			BVHAccelTreeNode *child, *lastChild;
			// Left Child
			child = BuildHierarchy(list, splits[0], splits[1], splitAxis);
			parent->leftChild = child;
			parent->bbox = child->bbox;
			lastChild = child;

			// Add remaining children
			for (unsigned int i = 1; i < splits.size() - 1; i++) {
				child = BuildHierarchy(list, splits[i], splits[i + 1], splitAxis);
				lastChild->rightSibling = child;
				parent->bbox = Union(parent->bbox, child->bbox);
				lastChild = child;
			}
			*/
			return parent;

		};
		void  BvhBuilder::FindBestSplit(cliext::vector<BVHAccelTreeNode ^>^ list, unsigned int begin, unsigned int end, float^% splitValue, unsigned int^% bestAxis)
		{

		};

		unsigned int BvhBuilder:: BuildArray(BVHAccelTreeNode ^node, unsigned int offset)
		{
			return 0;
		};
	}
}
